The present invention relates to techniques to search a number having a determined value in a set of numbers and more particularly to a method and circuits for searching the number having the minimum/maximum value in this set of numbers. The described solution allows a very fast search, improving thereby the response time and also providing a constant time response whatever the quantity of numbers among said set in which the minimum/maximum search is conducted.
In today""s computing processes, the search of the minimum or maximum value among a set of numbers is extensively performed in various technical fields such as in optimization, artificial neural networks, signal processing, etc. The resulting value is used in subsequent computation tasks or to undertake any appropriate action, e.g. to select a circuit associated thereto. Because, it is highly desirable that the search must be performed as fast as possible, this objective can only be met by using high performance and expensive dedicated circuits. To date, several solutions exist to solve this acute problem, that are implemented in hardware, typically in a silicon chip, with more or less difficulty.
For instance, the most known method to determine the number having the minimum value among a set of numbers consists in comparing a number with another number of the set, selecting the number having the lowest value and then proceeding the same way with the selected number until all the numbers of the set have been processed, to identify the number(s) having the minimum value. obviously, this solution which requires a lot of processing steps that are sequentially performed is not optimized and presents major drawbacks. As known for those skilled in the art, the response time is prohibitive. This solution, and more generally all solutions that are derived therefrom, have response time that are not acceptable for most applications to date mainly because they are based on sequential processing algorithms. Moreover, the response time is degraded because it is function of the precision (the number q of bits used to code said numbers) and also depends upon the quantity of numbers in which the minimum/maximum value is searched.
Another approach consists in a simultaneous evaluation (i.e. in a parallel way) of all the bits of a same weight for the totality of the numbers in which the minimum/maximum value is searched. Such a parallel approach has been recently described in the technical literature in connection with an advanced family of neural silicon chips that are manufactured and commercialized by IBM France under the ZISC036 label (ZISC is a registered Trade Mark of IBM Corp). For more details, one may refer to U.S. Pat. No. 5,740,326 entitled xe2x80x9cCircuit for Searching/Sorting Data in Neural Networksxe2x80x9d assigned to the same assignee.
The principle of this approach will be briefly explained by reference to FIG. 1, assuming that p numbers (referred to hereinbelow as Number 1 to Number p) coded on q bits are processed. Now turning to FIG. 1, circuit 10 which is comprised of p blocks 11 referenced 11-1 to 11-p (one per Number to be searched) processes a one bit slice, in this case the second bit (bit 2 or Bit2) of said Numbers. Note that all the q slices are of identical construction. In essence, a block 11 is quite similar to the circuit shown in FIG. 28B of the above cited U.S. patent. For instance, block 11-1 comprises a two-way OR gate 12-1, a two-way AND gate 13-1 and a two-way OR gate 14-1. The two latter gates form sub-block 15-1 that has the key role of selecting/deselecting the Number associated thereto, Number 1 in this case. Using the same terminology as in the above cited U.S. patent, signals Exout1-2 and Bit1-2 are applied to OR gate 12-1. Signals Exout1-2 and Bit1-2 represent the state of Number 1 (i.e. selected or deselected) and the value of bit 2 for that Number 1 respectively. The same construction applies to all blocks 11-1 to 11-p. The outputs of OR gates 12-1 to 12-p are applied to a p-way AND gate 16 (AND gate 16 needs as many inputs as there are Numbers to be simultaneously processed) to produce a signal which is inverted in inverter 17. AND gate 16 and inverter 17 form block 18. The resulting signal is applied to a first input of all AND gates 13-1 to 13-p whose other input receives the corresponding Bit signal i.e. Bit1-2 to Bit1-2. The outputs of AND gates 13-1 to 13-p and the corresponding Exout signals, i.e. Exout1-2 to Exoutp-2 are applied to OR gates 14-1 to 14-p respectively. The signals that are output by OR gates 14-1 to 14-p are labeled Exout1-3 to Exoutp-3 to still remain consistent with that terminology. Block 18 which is common for all the p blocks 11-1 to 11-p allows to determine the minimum value for bit 2 of the p numbers, i.e. for one bit only. For example, in order to do this comparison to select the minimum value, each slice of one bit of all Numbers 1 to p is processed in sequence, one slice per step (e.g. per clock cycle) from the most significant bit (MSB) to the less significant bit (LSB). The response time of this method is then function of the quantity q of slices, i.e. the number of bits used to code Number 1 to Number p. Thus, this solution is parallel for what concerns the p Numbers and sequential for what concerns the q bits of coding. So that, whatever the value of p, the computational time depends only of the number of bits/slices q. As shown in FIG. 1, the Exout signal, representing the exclusion bit, is used to select/deselect the corresponding Number during the evaluation process. A Number is selected as long as the Exout signal is equal to a logic xe2x80x9c0xe2x80x9d and it is deselected as soon as it is equal to a logic xe2x80x9c1xe2x80x9d. As a matter of fact, if a Number, e.g. Number 1 has been deselected during the evaluation of bit i (i varies from 1 to q), Exout1-(i+1) is equal to xe2x80x9c1xe2x80x9d, all the next signals: Exout1-(i+2), . . . , Exout1-q will be set to xe2x80x9c1xe2x80x9d. As a result, Number 1 will not be taken into account anymore whatever its value and the values of signals Bit1-(i+1), . . . , Bit1-q are inhibited. Because, still in this example limited to the search of the minimum value, the first slice corresponding to bit 1 (i.e. the MSB) must not be deselected when the evaluation process starts, signals Exout1-1 to Exoutp-1 are forced to the logic xe2x80x9c0xe2x80x9d.
In summary, this solution requires as many steps as the quantity q of bits used to code Numbers 1 to p limiting thereby the search process speed and is clearly silicon room consuming.
It is therefore a primary object of the present invention to provide a method and circuits for performing the search of the minimum/maximum value among a set of numbers wherein the response time is significantly improved because several bit slices can be simultaneously processed in parallel in a same step.
It is another object of the present invention to provide a method and circuits for performing the search of the minimum/maximum value among a set of numbers wherein the response time is constant whatever the quantity of numbers among which the search is performed.
It is still another object of the present invention to provide a method and circuits for performing the search of the minimum/maximum value among a set of numbers which save a significant area when implemented in a silicon chip and simplify its connectivity.
The accomplishment of these and other related objects is achieved by the method and circuits according to the present invention.
The method for performing the search of the minimum/maximum value among a set of p numbers referred to as Numbers coded in a binary format on q bits comprises the steps of:
a) splitting each Number in K sub-values coded on n bits (q less than =Kxc3x97n) and defining a parameter k(k=1 to K) which assigns a rank to each sub-value of a Number, all the sub-values of a same rank forming a slice;
b) forming the first slice (k=1) composed by the n-bit coded sub-values of the first rank (MSBs);
c) encoding each n-bit coded sub-value of that slice on m bits (m greater than n) to form a slice of m-bit encoded sub-values using a coding technique that allows the minimum/maximum value evaluation by an elementary logical function (AND, OR);
d) searching in parallel among said slice of m-bit encoded sub-values to evaluate the minimum/maximum m-bit encoded sub-value thereof;
e) deselecting all the Numbers whose m-bit encoded sub-value is greater/lower than the minimum/maximum m-bit encoded sub-value that has been evaluated in step d); and,
f) repeating steps c) to d) with the next slice (k=k+1) of n-bit coded sub-values until all the slices have been processed (k=K) so that the minimum/maximum value is evaluated as corresponding to the value of the Number(s) not deselected.
The circuit for searching the minimum/maximum value among a set of p numbers referred to as Numbers coded in a binary format on q bits comprises:
a) minimum/maximum value evaluation means which consist of m p-way AND gates able to perform an AND function on each of the m bits of same weight of p m-bit coded binary words; and,
b) p blocks, each block being associated to a Number comprising:
a) splitting means to split each Number in K sub-values (K greater than =1) of n bits according to relation: q less than =Kxc3x97n;
b) encoding means connected to said splitting means to encode each n-bit coded sub-value on a m-bit encoded sub-value (m greater than n) and having its output connected to said minimum/maximum value evaluation means; and,
c) deselecting means connected to said encoding means;
wherein the coding technique used in the encoding means allows the minimum/maximum evaluation for the m-bit encoded sub-values generated by all the encoding means of the searching circuit through an AND function;
wherein the m-bit encoded sub-values generated by all the encoding means of the searching circuit are applied to the minimum/maximum value evaluation means to evaluate the minimum/maximum encoded sub-value among them and to the deselecting means to generate an exclusion signal Exout able to deselect the Number associated to this block when its m-bit encoded sub-value is greater/lower than the minimum/maximum m-bit encoded sub-value that has been evaluated.
The method of the present invention thus significantly improves the response time of the minimum/maximum value search by parallelizing most of the computations if not all, so that it is no longer dependent of the quantity q of bits to code the numbers to be searched so that the number of steps of the minimum/maximum evaluation process can be significantly inferior.
The novel features believed to be characteristic of this invention are set forth in the appended claims. The invention itself, however, as well as these and other related objects and advantages thereof, will be best understood by reference to the following detailed description to be read in conjunction with the accompanying drawings.